State Machines
State machines are sequential logic systems whose output signals are a function of previous and present input signals, in contrast to combinatorial logic systems whose output signals are a function of present input signals alone. State machines typically include one or more storage elements and occupy a plurality of states which are determined by input signals and the contents of the one or more storage elements. State. machines "move" sequentially between the states (that is, one state becomes inactive and another state becomes active) in response to the input signals and transition rules established by combinatorial logic, which defines a logic "path" between the states. State machines are typically incorporated into circuits which also include other combinatorial logic and sequential logic circuitry, and frequently serve as controllers.
FIG. 1 shows a bubble flow diagram of a state machine which includes seven states, STATE 1 to STATE 7. The state machine receives input signals A through E. As indicated in FIG. 1, the state machine remains in STATE 1 until one of two transition rules is satisfied: (1) if input signal A is high, B is high, and C is low, the state machine moves into STATE 4; (2) if input signal A is high, B is low and C is high, the state machine moves into STATE 2. Similarly, the state machine remains in STATE 4 until input signal A is high, B is high and C is low. From STATE 2, the state machine enters STATE 3 if input signal D is high, or enters STATE 4 if input signal D is low. The other transition rules resulting in movements between states are also indicated.
State machines are commonly implemented in programmable logic devices. Programmable logic devices include programmable array logic devices (PALs) and field programmable gate arrays (FPGAs).
The state of a typical state machine is defined by the states (high or low output signals) of a set of flip-flops which are part of the state machine. In PALS, which have wide combinatorial logic circuitry but relatively few flip-flops, state machines are typically implemented using a highly encoded system wherein the output signals of all of the flip-flops define the active state of the state machine. For example, four flip-flops are used to define 16 separate states of a 16-state machine. Another scheme, call one-hot encoding (OHE), is frequently used to implement state machines in FPGAs, which contain numerous flip-flops but limited fan-in capability. In OHE, each state is represented by a single flip-flop. Thus, 16 flips are used to define 16 separate states. As suggested by the name OHE, only one flip-flop associated with the state machine need be in a logical "1" (hot) state to represent the active state of the state machine. OHE requires a larger number of flip-flops than are required in the highly encoded systems implemented in PAL devices, but offers higher performance (speed) because there are fewer levels of logic between the flip-flops.